import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/4 21:18
 * @description 当遍历到i 时，如果[0..i]的最大值 < [i+1..]的最小值，那么肯定可以
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {5, 0, 3, 8, 6};
        solution.partitionDisjoint(nums);
    }

    public int partitionDisjoint(int[] nums) {
        int n = nums.length;
        int[] max = new int[n];
        int m = nums[0];
        for (int i = 0; i < n; i++) {
            if (nums[i] > m) {
                m = nums[i];
            }
            max[i] = m;
        }

        int[] min = new int[n];
        int in = nums[n - 1];
        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] < in) {
                in = nums[i];
            }
            min[i] = in;
        }
        for (int i = 0; i < n - 1; i++) {
            if (max[i] <= min[i + 1]) {
                return i + 1;
            }
        }
        return 0;
    }
}
